#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/8/25 15:47
# ===========================================
#       题目名称： 38. 外观数列
#       题目地址： https://leetcode.cn/problems/count-and-say/description/
#       题目描述： https://note.youdao.com/s/RRXNSXjR
# ===========================================


class Solution:
    """
        实现思路：
            1   - n = 1
            11  - n = 2     上面是1个1 - 11
            21  - n = 3     上面是2个1  -   21
            1211- n = 4     上面是1个2 1个1  1211
    """

    def countAndSay(self, n):
        if not 1 <= n <= 30:
            return 0
        stack = [1, ]  # 初始值
        n -= 1
        while n > 0:
            new_stack = []
            while stack:
                element = stack.pop(0)
                if not new_stack:
                    new_stack.append(1)
                    new_stack.append(element)
                elif new_stack[-1] == element:
                    new_stack[-2] += 1
                else:
                    new_stack.append(1)
                    new_stack.append(element)

            stack = new_stack
            n -= 1
        return "".join([str(stack[i]) for i in range(len(stack))])


if __name__ == '__main__':
    s = Solution()
    # 1
    print(s.countAndSay(n=1))
    # 11
    print(s.countAndSay(n=2))
    # 21
    print(s.countAndSay(n=3))
    # 1211
    print(s.countAndSay(n=4))
    # 111221
    print(s.countAndSay(n=25))
